package leetcode_jz_offer;

/**
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题
 **/
public class Num16_数值的整数次方 {
    //方法1：递归
    public double myPow(double x, int n) {
        long N=n;
        //x^n,n>=0时正常计算，n<=0时先N=-N,再在最后结果上求倒数即得到结果：eg:2^2=4;2^-2=1/(-(-2))^2=1/4
        return N>=0?quickMul(x,N):1.0/quickMul(x,-N);
    }

    private double quickMul(double x, long N) {
        if(N==0){
            return 1;
        }
        double res=quickMul(x,N/2);
        return N%2==0?res*res:res*res*x;
    }

    //方法2：迭代
    public double myPow1(double x, int n) {
        long N=n;
        //x^n,n>=0时正常计算，n<=0时先N=-N,再在最后结果上求倒数即得到结果：eg:2^2=4;2^-2=1/(-(-2))^2=1/4
        return N>=0?quickMul1(x,N):1.0/quickMul1(x,-N);
    }

    private double quickMul1(double x, long N) {
        double res=1.0;
        // 贡献的初始值为 x
        double x_con=x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N>0){
            if(N%2==1){
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                res*=x_con;
            }
            // 将贡献不断地平方
            x_con*=x_con;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N/=2;
        }
        return res;
    }

}
